package com.dyz.LeetCodeforSwordFingerOffer;

import java.util.HashMap;

/**
 * @ClassNamebuildTree07
 * @Description
 * @Author: daiyizheng
 * @Date2021/6/13 5:38 下午
 * @Version V1.0
 **/
public class buildTree07 {
    //利用原理，前序遍历的第一个节点就是子树的根，在中序遍历通过根，区分哪些是左子树，哪些是右子树
    //左右子树
    HashMap<Integer, Integer> map = new HashMap<>();
    int [] preorder; //保留的前序遍历

    public TreeNode buildTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for(int i = 0; i<preorder.length; i++){
            map.put(inorder[i], i);
        }
        return recursive(0, 0, inorder.length-1);
    }

    private TreeNode recursive(int preRootIdx, int inLeftIdx, int inRightIdx) {
        //相等就是自己
        if(inLeftIdx>inRightIdx){
            return null;
        }
        //root_idx是在先序里面的
        TreeNode root = new TreeNode(preorder[preRootIdx]);
        // 有了先序的,再根据先序的，在中序中获 当前根的索引
        int idx = map.get(preorder[preRootIdx]);

        //左子树的根节点就是 左子树的(前序遍历）第一个，就是+1,左边边界就是left，右边边界是中间区分的idx-1
        root.left = recursive(preRootIdx+1, inLeftIdx, idx-1);

        //由根节点在中序遍历的idx 区分成2段,idx 就是根

        //右子树的根，就是右子树（前序遍历）的第一个,就是当前根节点 加上左子树的数量
        // pre_root_idx 当前的根  左子树的长度 = 左子树的左边-右边 (idx-1 - in_left_idx +1) 。最后+1就是右子树的根了

        root.right = recursive(preRootIdx + (idx-1 - inLeftIdx +1)  + 1, idx+1, inRightIdx);
        return root;
    }


    //
    public TreeNode buildTree1(int[] preorder, int[] inorder){
        if(preorder==null|| preorder.length==0||inorder==null||inorder.length==0){
            return null;
        }

        //前序数组的每个值是子树的根节点
        //前序的值在中序对应的值将中序切分为左右子树
        return dfs(preorder, inorder,0, preorder.length-1, 0, inorder.length-1);

    }

    private TreeNode dfs(int[] preorder, int[] inorder, int pStart, int pEnd, int iStart, int iEnd){
        //递归结束边界
        if (pStart>pEnd || iStart> iEnd){
            return null;
        }

        TreeNode root = new TreeNode(preorder[pStart]);
        //计算中序遍历的中间值
        int mid=iStart;//inorder的起始位置
        while(mid<=iEnd){
            if(preorder[pStart]==inorder[mid]){
                break;
            }
            mid++;
        }

        int leftCount = mid-iStart;

        //左右节点
        root.left = dfs(preorder, inorder, pStart+1, pStart+leftCount, iStart,  mid-1);//前序的左边， 中序的左边
        root.right = dfs(preorder, inorder, pStart+leftCount+1, pEnd, mid+1, iEnd);
        return root;
    }

    //根据后续和中序确定二叉树
    public TreeNode buildTree2(int[] inorder, int[] postorder, int iStart, int iend, int pStart, int pend){
        if(iStart>iend || pStart>pend){
            return null;
        }
        //构建新的root节点 /后续遍历序列的最后一个为根
        TreeNode root =new TreeNode(postorder[pend]);
        int mid=iStart;
        while(mid<=iend && inorder[mid]!=root.val){
            mid++;
        }
        int leftCount=mid-iStart;
        root.left=buildTree2(inorder, postorder, iStart, mid-1, pStart, pStart+leftCount-1);
        root.right=buildTree2(inorder,postorder,mid+1, iend, pStart+leftCount, pend-1);
        return root;
    }
}
